package solution;

import java.util.Arrays;
//https://leetcode.cn/problems/minimum-size-subarray-sum/submissions/416565145/

////暴力解法，时间会超时
//class Solution {
//    public int minSubArrayLen(int target, int[] nums) {
//    	int n = nums.length;
//    	if (n == 0) {
//    		return 0;
//    	}
//    	int ans = Integer.MAX_VALUE;
//    	for (int i = 0; i < n; i++) {
//    		int sum = 0;
//    		for (int j = i; j < n; j++) {
//    			sum += nums[j];
//    			if (sum >= target) {
//    				ans = Math.min(ans, j - i + 1);
//    				break;
//    			}
//    		}
//    	}
//		return ans == Integer.MAX_VALUE ? 0 : ans;
//
//    }
//}

//二分法搜索
//class Solution {
//    public int minSubArrayLen(int target, int[] nums) {
//    	int n = nums.length;
//    	if (n == 0) {
//    		return 0;
//    	}
//    	int[] sums = new int[n + 1];
//    	for (int i = 1; i < sums.length; i++) {
//    		sums[i] = sums[i - 1] + nums[i - 1];
//    	}
//    	int ans = Integer.MAX_VALUE;
//    	for (int i = 1; i <= n; i++) {
//			int temp = target + sums[i - 1];
//			int bound = Arrays.binarySearch(sums, temp);//返回的是该插入位置的负下标（从1开始计数，然后 × -1）
//			if (bound < 0) {
//				bound = -bound - 1;
//			}
//			if (bound <= n) {
//				ans = Math.min(ans, bound - i + 1); 
//			}
//		}
//    	return ans == Integer.MAX_VALUE ? 0 : ans;
//    }
//    public static void main(String[] args) {
//		int[] arr = {1, 3, 4, 5, 6, 10};
//		int a = -5;
//		System.out.println(-a);
//		System.err.println(Arrays.binarySearch(arr, 7));
//	}
//}


//滑动窗口
class Solution {
    public int minSubArrayLen(int target, int[] nums) {
    	int n = nums.length;
    	if (n == 0) {
    		return 0;
    	}
    	int ans = Integer.MAX_VALUE;
    	int start = 0;
    	int end = 0;
    	int sum = 0;
    	while (end < n) {
    		sum += nums[end];
    		while (sum >= target) {
    			ans = Math.min(ans, end - start + 1);
    			sum -= nums[start];
    			start++;
    		}
    		end++;
    	}
    	return ans == Integer.MAX_VALUE ? 0 : ans;
    }
}